Suchergebnisse

This work develops a generic framework, called the bag-of-paths (BoP), for link and network data analysis. The central idea is to assign a probability distribution on the set of all paths in a network. More precisely, a Gibbs–Boltzmann distribution is defined over a bag of paths in a network, that is, on a representation that considers all paths independently. We show that, under this distribution, the probability of drawing a path connecting two nodes can easily be computed in closed form by simple matrix inversion. This probability captures a notion of relatedness, or more precisely accessibility, between nodes of the graph: two nodes are considered as highly related when they are connected by many, preferably low-cost, paths. As an application, two families of distances between nodes are derived from the BoP probabilities. Interestingly, the second distance family interpolates between the shortest-path distance and the commute-cost distance. In addition, it extends the Bellman–Ford formula for computing the shortest-path distance in order to integrate sub-optimal paths (exploration) by simply replacing the minimum operator by the soft minimum operator. Experimental results on semi-supervised classification tasks show that both of the new distance families are competitive with other state-of-the-art approaches. In addition to the distance measures studied in this paper, the bag-of-paths framework enables straightforward computation of many other relevant network measures.

International audience ; We present the comparison and combination of two different semi automatic classification methods: an original linguistic based analysis, named extended lexical patterns (motifs lexicaux étendus, MLE) and a machine learning approach (SVM). Classification is supervised because of the use of a thesaurus containing the definition of categories. First, both systems are used and evaluated separately on the same real dataset: law and parliament documents in French. Quite unexpectedly, MLE performs as well as a state-of-the-art method such as SVM. During the second step, the combined method gave a performance improvement which underlines the complementarities of both basis methods. ; Dans le contexte de l'indexation semi-automatique de textes, nous présentons la comparaison et la combinaison de deux méthodes de classification mettant en oeuvre des approches différentes : analyse par une méthode originale à forte composante linguistique que nous nommons motifs lexicaux étendus (MLE) d'une part et apprentissage artificiel SVM d'autre part. La classification est de type supervisée car elle exploite un ensemble de catégories définies par un thésaurus documentaire. Dans un premier temps, les deux systèmes sont appliqués et évalués séparément sur un même jeu de données réelles, des textes de type législatif et parlementaire en français. De manière quelque peu inattendue, la méthode MLE permet d'atteindre des performances tout à fait compétitives par rapport à la technique state-of-the-art que constitue SVM. Les méthodes sont ensuite combinées dans le but d'obtenir une performance finale supérieure aux performances individuelles. Le gain obtenu indique une complémentarité entre les deux méthodes.